//
// Created by yanhai on 2021/1/3.
//

// 简单选择排序

#include <stdio.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 和冒泡排序的遍历方式差不多，但是比较2个元素需要交换时，选择排序只是将它记下来
// 找到当前遍历完一遍时最小的元素，然后再交换
// 这样，最好的情况下，交换次数为0，最差的情况下交换次数为n-1，
// 但是无论最好最差情况下，比较次数都是固定的，=n-1+n-2+...+1=n(n-1)/2
// 时间复杂度依然为O(n^2)，和冒泡排序一样，但是性能上还是略优于冒泡排序
// 简单选择排序最大的特点就是交换移动数据的次数相当少
// 简单选择排序是不稳定的，因为当两个元素交换时，假如前面的这个元素被交换到了最后一位，那么原本在它后面的相同值的元素就跑到它前面去了。
void select_sort(int *data, int length)
{
    int i = 0, j = 0;
    for (i = 0; i < length - 1; i++) {
        int min = i;  // 假定当前剩下的n个元素，第一个是最小的
        for (j = i + 1; j < length; j++) {
            // 找到比当前记录的最小值还小
            if (data[min] > data[j]) {
                min = j;
            }
        }
        // 遍历完了一次，找到了最小值的下标就是min，如果min不是第一个，则和第一个交换，使第一个元素是最小的
        if (min != i) {
            swap(&data[i], &data[min]);
        }
        // 然后将剩下的n-i个元素也按这样的方式排序
    }
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    select_sort(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
